package com.xiyou.week01.linked;

/**
 * 25. K 个一组翻转链表
 *
 * @ClassName：LeetCode25
 * @Author：西柚
 * @Date：2021/11/16 11:26 下午
 * @Versiion：1.0
 */
public class ReverseKGroup {

    /**
     * 输入：head = [1,2,3,4,5], k = 2
     * 输出：[2,1,4,3,5]
     *
     * @param head
     * @param k
     * @return
     */
    public static ListNode reverseKGroup(ListNode head, int k) {

//        ListNode protect = new ListNode(0, head);
        ListNode protect = new ListNode(0);
        ListNode last = protect;
        // 分组遍历
        while (head != null) {
            // 1.分组（往后走K-1步，找到一组）
            // 一组开头head    结尾end
            ListNode end = getEnd(head, k);
            if (end == null) {
                break;
            }

            ListNode nextGroupHead = end.next;

            // 2.一组内部（head 到 end 之间）要反转（调用反转链表）
            reverseList(head, nextGroupHead);

            // 3.跟下每组跟前一组、后一组的边
            last.next = end;
            head.next = nextGroupHead;

            last = head;
            head = nextGroupHead;
        }

        return protect.next;
    }

    /**
     * 反转链表，在节点stop停止
     *
     * @param head
     * @return
     */
    private static ListNode reverseList(ListNode head, ListNode stop) {
        ListNode last = head;
        head = head.next;
        while (head != stop) {
            ListNode nextHead = head.next;
            head.next = last;
            last = head;
            head = nextHead;
        }
        return last;
    }

    /**
     * 返回走K-1步之后的节点
     * 返回null表示不够K个
     *
     * @param head
     * @param k
     * @return
     */
    private static ListNode getEnd(ListNode head, int k) {
        while (head != null) {
            k--;
            if (k == 0) {
                return head;
            }
            head = head.next;
        }
        return null;
    }

//    class ListNode {        //类名 ：Java类就是一种自定义的数据结构
//        int val;            //数据 ：节点数据
//        ListNode next;      //对象 ：引用下一个节点对象。在Java中没有指针的概念，Java中的引用和C语言的指针类似
//
//        ListNode(int val) {  //构造方法 ：构造方法和类名相同
//            this.val = val;   //把接收的参数赋值给当前类的val变量
//        }
//    }

    //打印输出方法
    static void print(ListNode listNoed) {
        //创建链表节点
        while (listNoed != null) {
            System.out.println("节点:" + listNoed.val);
            listNoed = listNoed.next;
        }
        System.out.println();
    }

    public static void main(String[] args) {
        ListNode nodeSta = new ListNode(1);    //创建首节点
        ListNode nextNode;                     //声明一个变量用来在移动过程中指向当前节点
        nextNode = nodeSta;                      //指向首节点

        //创建链表
        ListNode node = new ListNode(2);  //生成新的节点
        nextNode.next = node;               //把心节点连起来
        nextNode = nextNode.next;           //当前节点往后移动

        node = new ListNode(3);        //生成新的节点
        nextNode.next = node;               //把心节点连起来
        nextNode = nextNode.next;           //当前节点往后移动

        node = new ListNode(4);        //生成新的节点
        nextNode.next = node;               //把心节点连起来
        nextNode = nextNode.next;           //当前节点往后移动

        node = new ListNode(5);        //生成新的节点
        nextNode.next = node;               //把心节点连起来
        nextNode = nextNode.next;           //当前节点往后移动

        print(nodeSta);

        print(reverseKGroup(nodeSta, 2));
    }

}
